package util;

import graph.GraphFile;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

import settings.Global;
import testbench.Driver;

/**
 * Breadth-first search static functions
 * 
 * @author Jonathan
 * 
 */
public class BFS
{
    private static List<Integer> linksList;

    /**
     * Traverse n levels deep from v1 and v2 and find the pages that are in common at those levels.
     * 
     * @param g
     *            GraphFile object
     * @param v1
     *            First starting page
     * @param v2
     *            Second starting page
     * @param level
     *            Levels to traverse
     * @return List of common pages at the nth level
     */
    public static List<Integer> BFSCommonNLevels(GraphFile g, int v1, int v2, int level)
    {
	List<Integer> list1 = traverseNLevels(g, v1, level);
	list1 = Driver.removeDuplicatesAndSort(list1);
	List<Integer> list2 = traverseNLevels(g, v2, level);
	list2 = Driver.removeDuplicatesAndSort(list2);

	// to iterate
	ListIterator<Integer> l1 = list1.listIterator();
	ListIterator<Integer> l2 = list2.listIterator();

	List<Integer> inCommon = new LinkedList<Integer>();

	int l1val = l1.next();
	int l2val = l2.next();

	while (l1.hasNext() && l2.hasNext())
	{// go until the end of a list
	    if (l1val == l2val)
	    {
		inCommon.add(l1val);
		l1val = l1.next();
		l2val = l2.next();
	    }
	    else if (l1val > l2val)
	    {
		l2val = l2.next();
	    }
	    else
	    {
		l1val = l1.next();
	    }
	}

	return inCommon;
    }

    /**
     * Traverse graph using BFS only going n-levels down. Wrapper function for traverseNLevelsHelper()
     * 
     * @param g
     *            GraphFile object
     * @param v
     *            Starting page number
     * @param level
     *            Number of levels to traverse before stopping
     * @return LinkedList of pages found at the deepest level
     */
    public static List<Integer> traverseNLevels(GraphFile g, int v, int level)
    {
	if (g == null)
	    return new LinkedList<Integer>(); // empty

	linksList = new LinkedList<Integer>();
	traverseNLevelsHelper(g, v, level, 0);
	Driver.removeDuplicatesAndSort(linksList);

	return linksList;
    }

    /**
     * Helps traverseNLevels() function
     * 
     * @param g
     *            GraphFile object
     * @param v
     *            Source page number
     * @param targetLevel
     *            Target level
     * @param currentLevel
     *            Current level in recursion
     */
    private static void traverseNLevelsHelper(GraphFile g, int v, int targetLevel, int currentLevel)
    {
	if ((targetLevel - 1) == currentLevel)
	{
	    linksList.addAll(g.getOutgoingLinks(v));
	}
	else
	{
	    for (int w : g.getOutgoingLinks(v))
		traverseNLevelsHelper(g, w, targetLevel, currentLevel + 1);
	}
    }

    /**
     * Traverses the entire graph staring from vertex v.
     * 
     * @param g
     *            GraphFile object
     * @param v
     *            Starting article page number
     * @return Number of Pages this page can reach in a traversal
     */
    public static int traverse(GraphFile g, int v)
    {
	Global.BFSPagesReached = 0;
	if (g == null)
	    return 0;

	System.out.println("Running BFS Traversal...");
	HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
	HashMap<Integer, Integer> edgeTo = new HashMap<Integer, Integer>();
	LinkedList<Integer> queue = new LinkedList<Integer>();

	queue.add(v);
	visited.put(v, true);

	while (!queue.isEmpty())
	{
	    int current = queue.pop();
	    // System.out.println(g.getPageName(current)); //do not print for faster result
	    Global.BFSPagesReached++;
	    // if(Global.BFSPagesReached%1000==0)
	    // System.out.println(Global.BFSPagesReached);
	    for (int w : g.getOutgoingLinks(current))
	    {
		if (!visited.containsKey(w))
		{
		    queue.add(w);
		    visited.put(w, true);
		    edgeTo.put(w, v);
		}
	    }
	}
	return Global.BFSPagesReached;
    }

    /**
     * Uses BFS to traverse the graph from start vertex and stops when it finds the end vertex.
     * 
     * @param g
     *            GraphFile object
     * @param start
     *            Starting page number
     * @param end
     *            Ending page number
     * @return Path from start to end
     */
    public static LinkedList<Integer> findPath(GraphFile g, int start, int end)
    {
	if (g == null)
	    return null;

	System.out.println("Running BFS Find Path...");
	HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
	HashMap<Integer, Integer> edgeTo = new HashMap<Integer, Integer>();
	LinkedList<Integer> queue = new LinkedList<Integer>();
	LinkedList<LinkedList<Integer>> path = new LinkedList<LinkedList<Integer>>(); // determining path
	LinkedList<Integer> currentPath = new LinkedList<Integer>();// current path
	currentPath.add(start);

	queue.add(start);
	path.add(currentPath);// add current Path
	visited.put(start, true);

	while (!queue.isEmpty())
	{
	    int current = queue.pop();
	    LinkedList<Integer> currentP = path.pop();// get the current path
	    // System.out.println(g.getPageName(current)); //prints out the page name that is currently visited
	    for (int w : g.getOutgoingLinks(current))
	    {
		if (!visited.containsKey(w))
		{
		    queue.add(w);
		    LinkedList<Integer> lli_temp = (LinkedList<Integer>) currentP.clone();// copy it
		    lli_temp.add(w);// add to the path
		    path.add(lli_temp);
		    visited.put(w, true);
		    edgeTo.put(w, start);
		    if (w == end)
		    {
			return lli_temp;
		    }
		}
	    }
	}
	return null;
	// return new LinkedList<Integer>();
    }

}
